#include<iostream>

//策略模式

//具有纯虚函数的类：抽象类：不允许实例化对象
class Sort
{
public:
    virtual void sort(int*a,int size)=0;


};
//没实现父类的纯虚函数，子类任然是抽象类
class BubbleSort:public Sort
{
public:
    void sort(int*a,int size)
    {
        for (int i = 0; i < size; i++)
        {
        for (int j = 0; j < size-1-i; j++)
        {   if(a[j]>a[j+1])
            std::swap(a[j],a[j+1]);
        }
        
        }
    }

};

class FastSort:public Sort
{
public:
    void sort(int*a,int size)
    {
        FSort(a,0,size-1);
    }
private:
    void FSort(int *a,int start,int end)
    {
          if (start>=end)
    {
        return;
    }
    int left=start;
    int right=end;
    int temp=a[left];
      
    while (left<right)
    {
        //先右边动,找比基准值小
        while (a[right]>temp&&left<right)
        {
            right--;
        }
         //把右边的值赋给左边空位
        if(left<right)
        {
            a[left++]=a[right];
        }
        while (a[left]<temp&&left<right)
        {
            left++;
        }
        if(left<right)
        a[right--]=a[left];

    }
    a[left]=temp;
    FSort(a,start,left-1);
    FSort(a,left+1,end);



    }
};

void S(Sort*s)
{
    int a[]={3,1,2};
    s->sort(a,3);
    for (int i = 0; i < 3; i++)
    {
        std::cout<<a[i]<<std::endl;
    }
    
}


int main()
{
    Sort *s1=new BubbleSort;
    Sort*s2 =new FastSort;
    S(s1);
    return 0;
    

}